#include <utstring.h>
#include <stdio.h>

char *id2str[26 * 26 * 26];

int str2id(char *a) {
    int ret = 0;
    for (int i = 2; i >= 0; i--) {
        ret = ret * 26 + a[i] - 'A';
    }
    return ret;
}

int cmp(const void *_a, const void *_b) {
    int **a = (int **) _a, **b = (int **) _b;
    return (*b)[0] - (*a)[0] ? (*b)[0] - (*a)[0] : (*b)[1] - (*a)[1];
}

int *vec[26 * 26 * 26];
int vec_len[26 * 26 * 26];
int *stk;
int stk_len;

void dfs(int curr) {
    while (vec_len[curr] > 0) {
        int tmp = vec[curr][--vec_len[curr]];
        dfs(tmp);
    }
    stk[stk_len++] = curr;
}

char **findItinerary(char ***tickets, int ticketsSize, int *ticketsColSize, int *returnSize) {
    memset(vec_len, 0, sizeof(vec_len));
    stk = malloc(sizeof(int) * (ticketsSize + 1));
    stk_len = 0;

    int *tickets_tmp[ticketsSize];
    for (int i = 0; i < ticketsSize; i++) {
        tickets_tmp[i] = (int *) malloc(sizeof(int) * 2);
        tickets_tmp[i][0] = str2id(tickets[i][0]);
        tickets_tmp[i][1] = str2id(tickets[i][1]);
        id2str[tickets_tmp[i][0]] = tickets[i][0];
        id2str[tickets_tmp[i][1]] = tickets[i][1];
    }
    qsort(tickets_tmp, ticketsSize, sizeof(int *), cmp);

    int add = 0;
    while (add < ticketsSize) {
        int adds = add + 1, start = tickets_tmp[add][0];
        while (adds < ticketsSize && start == tickets_tmp[adds][0]) {
            adds++;
        }
        vec_len[start] = adds - add;
        vec[start] = malloc(sizeof(int) * vec_len[start]);
        for (int i = add; i < adds; i++) {
            vec[start][i - add] = tickets_tmp[i][1];
        }
        add = adds;
    }

    dfs(str2id("JFK"));

    *returnSize = ticketsSize + 1;
    char **ret = malloc(sizeof(char *) * (ticketsSize + 1));
    int * tmp = stk;
    for (int i = 0; i < stk_len; ++i) {
        printf(" i   = %d, strk = %d\n", i, stk[i]);
    }
    for (int i = 0; i <= ticketsSize; i++) {
        ret[ticketsSize - i] = id2str[stk[i]];
    }
    return ret;
}

void setNum(char ***p, int num, int arr[2][3][4]) {
    int i;
    char **temp = NULL;
    if (p == NULL) {
        return;
    }
    temp = (char **) malloc(5 * sizeof(char *));
    for (i = 0; i < num; i++) {
        temp[i] = (char *) malloc(100 * sizeof(char));
        sprintf(temp[i], "%d%d%d", i, i, i);
    }
    *p = temp;//三级指针*p表示二级指针内存中保存的地址。
    //通过给*p赋值可以间接改变指针的指向
}

int main() {
    char test[4][2][3] = {{"MUC", "LHR"},
                          {"JFK", "MUC"},
                          {"SFO", "SJC"},
                          {"LHR", "SFO"}};
    int ticketsColSize = 0;
    int returnSize = 0;


    int count = 0;
    for (int i = 0; i < 4; i++) {
//        temp[i] = (char *) malloc(100 * sizeof(char));
//        sprintf(temp[i], "%d%d%d", i, i, i);
//        temp[i] = (char *) malloc(2 * sizeof(char));

        for (int j = 0; j < 2; ++j) {
//            printf("count = %d, str = %s%s\n", count, test[i][j], "\0");
//            count++;
            for (int k = 0; k < 3; ++k) {
                printf("%c  ", test[i][j][k]);
            }
            printf("\n");
        }
    }

    printf("=================================\n");

//    char **temp;
//    temp = (char **) malloc(4 * sizeof(char *));
//    for (int i = 0; i < 4; i++) {
//        temp[i] = (char *) malloc(6 * sizeof(char));
////            memset(temp[i], ch + i, sizeof(char) * 3);
//        memcpy(temp[i], test[i], 6 * sizeof(char));
////            temp[i] = test[i][j];
//    }
//
//    char ***p;
//    p = &temp;

    char ***p;
    p = (char ***) malloc(4 * sizeof(char **));
    for (int i = 0; i < 4; ++i) {
        p[i] = (char **) malloc(2 * sizeof(char *));
        for (int j = 0; j < 2; ++j) {
            p[i][j] = malloc(3 * sizeof(char));
            memcpy(p[i][j], test[i][j], 3 * sizeof(char));
        }
    }

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 2; ++j) {
            /*
            for (int k = 0; k < 3; ++k) {
                printf("  %s  \n", temp[i] + k);

            }
             */
//            printf("  %s  \n", p[i][j]);
            for (int k = 0; k < 3; ++k) {
                printf("%c  ", p[i][j][k]);
            }
            printf("\n");
        }
    }
//    for (int i = 0; i < 4; i++) {
//
//        for (int j = 0; j < 2; ++j) {
//            printf("  test i= %d j = %d  point = %p\n", i, j, test[i][j]);
//            printf("  temp i= %d j = %d  point = %p\n", i, j, temp[i]);
//            for (int k = 0; k < 3; ++k) {
//
//                printf("%c  ", (char)(p[i][j][k]));
//            }
//            printf("\n");
//        }
//    }
//    for (int i = 0; i < 4; ++i) {
//        char **retStr = p[i];
//        for (int j = 0; j < 2; ++j) {
//            char *pst = retStr[i];
//            for (int k = 0; k < 3; ++k) {
//                printf("%c ",(char)(pst + k));
//            }
//            printf("\n");
//        }
//
//    }


//    for (int i = 0; i < 2; ++i) {
//        for (int j = 0; j < 3; ++j) {
////            memcpy(**p + 1, test[i][j], 5);
//            **p + 1 = test[i][j];
//        }
//    }

//    *p = temp;
    printf("===============end=============\n");
    char **ret = findItinerary(p, 4, &ticketsColSize, &returnSize);
    for (int i = 0; i < returnSize; ++i) {
        for (int j = 0; j < 3; ++j) {
            printf("%c ", ret[i][j]);
        }
        printf("\n");
    }
}

//    int a[2][3][4] = {1, 3, 4};
//    int ***b = (int ***) new int[2];
//    for (inti = 0; i < 2; i++) {
//        b[i] = (int **) new int[3];
//        for (int j = 0; j < 3; j++) {
//            b[i][j] = new
//            int[4];
//        }
//    }
//    int i[2][2][2]={1,2,3,4,5,6,7,8};
//    int (*pi)[2][2];
//    int **pi1=(int **)i;
//
//    int a[2][3][4] = {1,2,3,4,5,6,7,8};
//    int (*b)[3];
//        for (int j = 0; j < 3; ++j) {
//            b[j] = a[j];
//    }
//    for (int i = 0; i < 2; i++) {
//        for (int j = 0; j < 3; j++) {
//            for (int k = 0; k < 4; k++) {
//                b[i][j][k] = a[i][j][k];
//            }
//        }
//    }


void singnMemo1(char ***p, int num) {
    int i;
    char **temp = NULL;
    if (p == NULL) {
        return;
    }
    temp = (char **) malloc(5 * sizeof(char *));
    for (i = 0; i < num; i++) {
        temp[i] = (char *) malloc(100 * sizeof(char));
        sprintf(temp[i], "%d%d%d", i, i, i);
    }
    *p = temp;//三级指针*p表示二级指针内存中保存的地址。
    //通过给*p赋值可以间接改变指针的指向
}

void freeMemo1(char ***p, int num) {
    int i;
    char **temp = NULL;
    if (p == NULL) {
        return;
    }
    temp = *p;//相当于把实参的地址赋值给临时变量
    for (i = 0; i < num; i++) {
        if (temp[i] != NULL) {
            free(temp[i]);//断开连接
            temp[i] = NULL;//内存制空
        }
    }
    free(temp);
    *p = NULL;//实参制空
}

int main1() {
    int i;
    int num = 5;
    char **p;
    p = (char **) malloc(num * sizeof(char *));
    singnMemo1(&p, num);

    for (i = 0; i < num; i++) {
        printf("  %s  \n", p[i]);
    }
    freeMemo1(&p, num);
    system("pause");
}